package pl.enigmatic.relationship;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.Vector;


public class GraphTS<V> {

	private final List<V> vertices = new Vector<V>();
	private final Map<V, Set<V>> edges = new HashMap<V, Set<V>>();

	public boolean addVertex(final V v) {
		if (!vertices.contains(v)) {
			vertices.add(v);
			if (!edges.containsKey(v)) {
				edges.put(v, new HashSet<V>());
			}
			return true;
		}
		return false;
	}

	public void addVertices(final List<V> list) {
		for (final V v : list) {
			addVertex(v);
		}
	}

	public void addEdge(final V from, final V to) {
		addVertex(from);
		addVertex(to);
		edges.get(from).add(to);
	}

	public boolean hasVertex(final V v) {
		return vertices.contains(v);
	}

	public boolean hasEgde(final V from, final V to) {
		return hasVertex(from) && edges.get(from).contains(to);
	}

	public List<V> topo() {// toplogical sort
		final List<V> res = new Vector<V>();

		while (!vertices.isEmpty()) // while vertices remain,
		{
			// get a vertex with no successors, or -1
			final V currentVertex = noSuccessors();
			if (currentVertex == null) {// must be a cycle
				return new Vector<V>();
			}
			// insert vertex label in sorted array (start at end)
			res.add(0, currentVertex);

			removeVertex(currentVertex); // delete vertex
		}

		return res;
	}

	public V noSuccessors() {// returns vert with no successors (or null if no such verts)
		for (final Entry<V, Set<V>> e : edges.entrySet()) {
			if (e.getValue().isEmpty()) { return e.getKey(); }
		}
		return null;
	}

	public void removeVertex(final V v) {
		edges.remove(v);
		for (final Set<V> set : edges.values()) {
			set.remove(v);
		}
		vertices.remove(v);
	}

	public static void main(final String[] args) {
		final GraphTS<Integer> g = new GraphTS<Integer>();
		g.addVertex(0); // 0
		g.addVertex(1); // 1
		g.addVertex(2); // 2
		g.addVertex(3); // 3
		g.addVertex(4); // 4
		g.addVertex(5); // 5
		g.addVertex(6); // 6
		g.addVertex(7); // 7

		g.addEdge(0, 3); // AD
		g.addEdge(0, 4); // AE
		g.addEdge(1, 4); // BE
		g.addEdge(2, 5); // CF
		g.addEdge(3, 6); // DG
		g.addEdge(4, 6); // EG
		g.addEdge(5, 7); // FH
		g.addEdge(6, 7); // GH

		for (final Object c : g.topo()) {
			System.out.print(c); // do the sort
		}
	}
}